package 图.无向图;

import 抽象数据类型.Graph;

/**
 * @description:
 * @author: ywk
 * @date: 2021-07-26
 */
public class 判断是否为无环图 {
    public static void main(String[] args) {
        int[] arr1 = {0, 1, 2, 0, 3, 4, 5, 6, 7, 9, 10, 11, 12};
        int[] arr2 = {6, 0, 0, 5, 5, 3, 4, 4, 8, 11, 9, 12, 9};
        Graph G = new Graph(arr1.length);
        G.addGraph(arr1, arr2);
        Cycle cc = new Cycle(G);
        System.out.println(cc.hasCycle);
    }
    public static class Cycle{
        private boolean[] marked;
        private boolean hasCycle;

        public Cycle(Graph graph) {
            marked = new boolean[graph.V()];
            for (int s = 0; s < graph.V(); s++) {
                if (!marked[s]) {
                    dfs(graph, s, s);
                }
            }
        }

        public void dfs(Graph graph,  int u,int v ){
            marked[v] = true;
            for (Integer w : graph.adj(v)) {
                if (!marked[w]) {
                    dfs(graph, v,w );
                } else if (w != u) {
                    hasCycle = true;
                }
            }
        }
        public boolean hasCycle() {
            return hasCycle;
        }
    }
}
